﻿using System;

namespace Merge_Sort
{
    public static class MergeSort
    {
        private static int[] data;        

        public static int[] Sort(int[] array)
        {
            data = array;

            SortArray(0, data.Length - 1);
            return data;
        }

        private static void SortArray(int low, int high)
        {
            if ((high - low) >= 1)
            {
                int middle1 = (low + high) / 2;
                int middle2 = middle1 + 1;

                SortArray(low, middle1);
                SortArray(middle2, high);

                Merge(low, middle1, middle2, high);
            }
        }

        private static void Merge(int left, int middle1, int middle2, int right)
        {
            int leftIndex = left;
            int rightIndex = middle2;
            int combinedIndex = left;
            int[] combined = new int[data.Length];

       

            while (leftIndex <= middle1 && rightIndex <= right)
            {
                if (data[leftIndex] <= data[rightIndex])
                    combined[combinedIndex++] = data[leftIndex++];
                else
                    combined[combinedIndex++] = data[rightIndex++];
            }

            if (leftIndex == middle2)
                while (rightIndex <= right)
                    combined[combinedIndex++] = data[rightIndex++];
            else
                while (leftIndex <= middle1)
                    combined[combinedIndex++] = data[leftIndex++];

            for (int i = left; i <= right; i++)
                data[i] = combined[i];
            
        }
    }
}
